package StringMatching;

public class KMP {
    public static int kmp(char[] source, int srcLength, char[] target, int tgtLength) {
        int[] next = getNext(target, tgtLength);
        int j = 0;
        for (int i = 0; i < srcLength; i++) {
            while (j > 0 && source[i] != target[j]) {
                j = next[j - 1] + 1;
            }
            if (source[i] == target[j]) j++;
            if (j == tgtLength) return i - tgtLength + 1;
        }
        return -1;
    }

    //求next数组
    private static int[] getNext(char[] target, int tgtLength) {
        int[] next = new int[tgtLength];
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < tgtLength; i++) {
            while (k != -1 && target[k + 1] != target[i]) {
                k = next[k];
            }
            if (target[k + 1] == target[i]) k++;
            next[i] = k;
        }
        return next;
    }
}
